#ifndef AVL_TREE_H_
#define AVL_TREE_H_

#include "avl_node.h"

#include <iostream>
using std::cout;
using std::endl;

template <typename T, bool duplicates>
class AVLTree {
public:
	AVLTree() : root(0) {}
	virtual ~AVLTree() {
		while (root != 0) {
			if (root->getTree(LEFT) != 0) {
				root = root->getTree(LEFT);
			} else if (root->getTree(RIGHT) != 0) {
				root = root->getTree(RIGHT);
			} else {
				AVLNode<T>* temp = root;
				root = root->getTree(PARENT);
				if (root){
					if (root->getTree(LEFT) == temp)
						root->disconnect(LEFT);
					else
						root->disconnect(RIGHT);
				}
				delete temp;
			}
		}
	}
	
	bool insert(const T& val) {
		bool res;
		if (root == 0){	//first node
			root = new AVLNode<T>(val);
			return true;
		}
		AVLNode<T>* curr = search(val, res);
		if (!duplicates && res) return false;
		if (res) {
			curr->incCounter();
			return true;
		}
		AVLNode<T>* newNode = new AVLNode<T>(val);
		newNode->connect(curr, PARENT);
		if ( val < curr->value()) 
			curr->connect(newNode, LEFT);
		else
			curr->connect(newNode, RIGHT);

		Balance(newNode);
		return true;	
	}

	//TEST FUNCTIONS

	void in_order(){ //??
		if (root) in(root); //??
	}

	void in(AVLNode<T>* curr){ ///?????
		if (curr->getTree(LEFT)) in(curr->getTree(LEFT));
		cout << curr->value() << endl;
		if (curr->getTree(RIGHT)) in(curr->getTree(RIGHT));

	}

	bool remove(const T& val){
		bool res, oneChild = false;
		NodeType nt;
		AVLNode<T>* curr = search(val, res);
		if (!res) return false;
		if ((duplicates) && (curr->dups() > 1)){
				curr->decCounter();
				return true;
		}
		
		if (curr->getTree(LEFT) && curr->getTree(RIGHT)){ //if curr has 2 sons
			AVLNode<T>* temp = getPrevInOrder(curr);
			curr->setValue(temp->value());
			curr->setDups(temp->dups());
		//	curr->connect(curr->getTree(LEFT), LEFT); // update Height & left children
		//	curr->connect(curr->getTree(RIGHT), RIGHT);
			curr = temp;
		}
		
		//check if the has only one son
		if (curr->getTree(LEFT)){
			if (!curr->getTree(RIGHT)) {
				nt = LEFT;
				oneChild = true;
			}
		} else{
			if (curr->getTree(RIGHT)){
				nt = RIGHT;
				oneChild = true;
			}
		}
		
		AVLNode<T>* parent = curr->getTree(PARENT);
		
		if (oneChild) (curr->getTree(nt))->connect(parent, PARENT);
		
		if (curr->isLeaf() || oneChild){
			if (root == curr){ 				
				root = oneChild ? root->getTree(nt) : 0;
				delete curr;
			} else {
				NodeType nt2;
				nt2 = ( parent->getTree(LEFT) == curr ) ? 
							LEFT : RIGHT;
				parent->disconnect(nt2);
				if (oneChild) (parent)->connect(curr->getTree(nt), nt2);
				delete curr;
			}
		}
		
		Balance(parent);
		return true;
	}

	//returns the number of elements that are smaller than the given value (-1 on error)
	int rank(const T& val) const{
		if (!root) return -1;
		AVLNode<T>* curr = root;
		int tot = 0;
		
		while (true) {		
			if (curr->isLeaf()) break;
			if (val < curr->value()) {
				if  (curr->getTree(LEFT) == 0) break;
				curr = curr->getTree(LEFT);

			} else {
				if  (curr->getTree(RIGHT) == 0) break;
				tot += curr->getLeftChildren() + curr->dups();
				curr = curr->getTree(RIGHT);

			}
		}
		
		if (val >= curr->value()) tot += curr->getLeftChildren() + curr->dups();
		
		return tot;
	}
	
	T getMin() const{
		if (!root) return false;
		AVLNode<T>* curr = root;
		while (curr->getTree(LEFT)) curr =	curr->getTree(LEFT);
		return curr->value();
	}
	
	//int dups(const T& val) const {} //is needed?
	
	/*bool exist (const T& val) const{ 
		bool b;
		search(val, b);
		return b;
	} */

protected:
	AVLNode<T>* root;
	
	enum RotType {NOROT, LL, LR, RR, RL};
	
	AVLNode<T>* search(const T& val, bool& result) const{
		AVLNode<T>* curr = root;
		if (root == 0) {
			result = false;
			return 0;
		}
		while (curr->value() != val) {
			if (curr->isLeaf()) {
				result = false;
				return curr;
			}
			if (val < curr->value()) {
				if  (curr->getTree(LEFT) == 0) {
					result = false;
					return curr;
				}
				curr = curr->getTree(LEFT);
			} else {
				if  (curr->getTree(RIGHT) == 0) {
					result = false;
					return curr;
				}
				curr = curr->getTree(RIGHT);
			}
		}
		result = true;
		return curr;
	}
	
	static int BF(AVLNode<T>* node) {
		int l = (node->getTree(LEFT) == 0) ? 0 : node->getTree(LEFT)->getHeight();
		int r = (node->getTree(RIGHT) == 0) ? 0 : node->getTree(RIGHT)->getHeight();
		return l-r;
	}
	
	static void connectParent(AVLNode<T>* node) {
		AVLNode<T>* parent = node->getTree(PARENT);
		if (parent == 0) return;
		if (node->value() < parent->value())
			parent->connect(node, LEFT);
		else 
			parent->connect(node, RIGHT);
	}
	
	static void RotateLeft(AVLNode<T>*& root) {
		AVLNode<T>* grand = root->getTree(PARENT);
		AVLNode<T>* lr = root->getTree(LEFT) == 0 ? 0 : (root->getTree(LEFT))->getTree(RIGHT);
		if (lr) lr->connect(root, PARENT);
		root->connect(root->getTree(LEFT), PARENT);
		root->connect(lr, LEFT);
		(root->getTree(PARENT))->connect(root, RIGHT);
		root = root->getTree(PARENT);
		root->connect(grand, PARENT);
		connectParent(root);
	}
	
	static void RotateRight (AVLNode<T>*& root) {
		AVLNode<T>* grand = root->getTree(PARENT);
		AVLNode<T>* rl = root->getTree(RIGHT) == 0 ? 0 : (root->getTree(RIGHT))->getTree(LEFT);
		if (rl) rl->connect(root, PARENT);
		root->connect(root->getTree(RIGHT), PARENT);
		root->connect(rl, RIGHT);
		(root->getTree(PARENT))->connect(root, LEFT);
		root = root->getTree(PARENT);
		root->connect(grand, PARENT);
		connectParent(root);
	}
	
	static RotType getRotType(AVLNode<T>* node){
		if (BF(node) == 2){
			if (BF(node->getTree(LEFT)) >= 0) 
				return LL;
			else 
				return LR;
		} else if (BF(node) == -2) {
			if (BF(node->getTree(RIGHT)) <= 0) 			
				return RR;
			else 
				return RL;
		}
		return NOROT;
	}
	
	//Balancing the tree after inserting the given node or deleting the node's child
	virtual void Balance(AVLNode<T>* node){
		AVLNode<T>* parent;
		AVLNode<T>* grand;
		AVLNode<T>* temp;
		
		if (!node || !root) return;
		
		// we first need to check the *current* node (not the parent)
		if (node->getTree(RIGHT))
			node = node->getTree(RIGHT);
		else if (node->getTree(LEFT))
			node = node->getTree(LEFT);
		
		while (node != root) {
			parent = node->getTree(PARENT);
			grand = parent->getTree(PARENT);
			RotType rot = getRotType(parent);
			switch (rot){
				case LL:	RotateLeft(parent);
							break;
				case LR:	temp = parent->getTree(LEFT);
							RotateRight(temp);
							RotateLeft(parent);
							break;
				case RR:	RotateRight(parent);
							break;
				case RL:	temp = parent->getTree(RIGHT);
							RotateLeft(temp);
							RotateRight(parent);
				default:	break;
			}
			
			if (rot == NOROT) connectParent(node);

			if (rot != NOROT && !grand) root = parent;
			else 
				connectParent(node);
	
			node = parent;
		}
	}
	
	// returns node before the given, in the InOrder scan
	static AVLNode<T>* getPrevInOrder(AVLNode<T>* node){
		AVLNode<T>* temp = node;
		temp = temp->getTree(LEFT);
		while (temp->getTree(RIGHT)) temp = temp->getTree(RIGHT);
		return temp;
	}

};
#endif /*AVL_TREE_H_*/
